package datastructure.structure;


import java.io.File;
import java.io.FileNotFoundException;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.Scanner;
import java.util.TreeSet;

/**
 * 基于 红黑树集合 的 邻接表
 *
 * @author or2
 * @Description 无向无权图
 * @create 2021年08月26日 时间: 16:40
 */
public class AdjList {

    private int V;
    private int E;
    private TreeSet<Integer>[] adj;

    /**
     * 从文件中获取图的数据
     *
     * @param fileName 文件夹名称
     */
    public AdjList(String fileName) {
        String baseDir = System.getProperty("user.dir");
        Path path = Paths.get(baseDir, "java", "datastructure", "src", "data");
        File file = new File(path + File.separator + fileName);

        try (Scanner scanner = new Scanner(file)) {
            V = scanner.nextInt();
            if (V < 0) {
                throw new IllegalArgumentException("顶点个数不能小于0!");
            }
//            邻接表数组 分配内存
            adj = new TreeSet[V];
//            邻接表属性 初始化
            for (int i = 0; i < V; i++) {
                adj[i] = new TreeSet<>();
            }
            E = scanner.nextInt();
            if (E < 0) {
                throw new IllegalArgumentException("边的个数不能小于0!");
            }

            for (int i = 0; i < E; i++) {
                int v1 = scanner.nextInt();
                int v2 = scanner.nextInt();
//                是否处理自环边?
                if (v1 == v2) {
                    throw new IllegalArgumentException("暂不处理自环边。");
                }
//                是否处理平行边?权值?
                if (adj[v1].contains(v2)) {
                    throw new IllegalArgumentException("不处理平行边。");
                }
//                将边加入表中
                adj[v1].add(v2);
                adj[v2].add(v1);
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }


    /**
     * 检测 两顶点间是否有边
     *
     * @param v1 顶点①
     * @param v2 顶点②
     * @return 存在边 -> true<br/>否则 -> false
     */
    boolean hasEdge(int v1, int v2) {
        checkVIndex(v1);
        checkVIndex(v2);
        return adj[v1].contains(v2);
    }

    /**
     * 查找该顶点的边
     *
     * @param v 被查找的顶点
     * @return 该顶点的边
     */
    public TreeSet<Integer> adj(int v) {
        return adj[v];
    }

    /**
     * 计算当前顶点的度
     * @param v 顶点
     * @return 顶点的度
     */
    public int degree(int v) {
        return adj(v).size();
    }

    /**
     * 检测 当前顶点下标是否越界
     *
     * @param vIndex 顶点下标
     */
    private void checkVIndex(int vIndex) {
        if (vIndex < 0 || vIndex >= V) {
            throw new IllegalArgumentException("顶点下标越界!");
        }
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();

        stringBuilder.append(String.format("顶点个数: %d, 边的个数: %d\n", V, E));
        for (int i = 0; i < V; i++) {
            stringBuilder.append(String.format("顶点 %d:\t", i));
            for (Integer integer : adj[i]) {
                stringBuilder.append(" " + integer);
            }
            stringBuilder.append("\n");
        }

        return stringBuilder.toString();
    }
}
